



<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      <meta http-equiv="x-ua-compatible" content="ie=edge">
      
        <meta name="description" content="Hrbust_ACM's Wiki">
      
      
        <link rel="canonical" href="https://hrbust-acm.online/Graph/ISAP/">
      
      
        <meta name="author" content="Hrbust_Acmer">
      
      
        <meta name="lang:clipboard.copy" content="复制">
      
        <meta name="lang:clipboard.copied" content="已复制">
      
        <meta name="lang:search.language" content="ja">
      
        <meta name="lang:search.pipeline.stopwords" content="True">
      
        <meta name="lang:search.pipeline.trimmer" content="True">
      
        <meta name="lang:search.result.none" content="没有找到符合条件的结果">
      
        <meta name="lang:search.result.one" content="找到 1 个符合条件的结果">
      
        <meta name="lang:search.result.other" content="# 个符合条件的结果">
      
        <meta name="lang:search.tokenizer" content="[\uff0c\u3002]+">
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-4.6.3">
    
    
      
        <title>ISAP算法 - Hrbust_ACM's Wiki</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/application.adb8469c.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/application-palette.a8b3c06d.css">
      
      
        
        
        <meta name="theme-color" content="#ef5350">
      
    
    
      <script src="../../assets/javascripts/modernizr.86422ebf.js"></script>
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto","Helvetica Neue",Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono","Courier New",Courier,monospace}</style>
      
    
    <link rel="stylesheet" href="../../assets/fonts/material-icons.css">
    
    
    
      
    
    
  </head>
  
    
    
    <body dir="ltr" data-md-color-primary="red" data-md-color-accent="blue">
  
    <svg class="md-svg">
      <defs>
        
        
          <svg xmlns="http://www.w3.org/2000/svg" width="416" height="448" viewBox="0 0 416 448" id="__github"><path fill="currentColor" d="M160 304q0 10-3.125 20.5t-10.75 19T128 352t-18.125-8.5-10.75-19T96 304t3.125-20.5 10.75-19T128 256t18.125 8.5 10.75 19T160 304zm160 0q0 10-3.125 20.5t-10.75 19T288 352t-18.125-8.5-10.75-19T256 304t3.125-20.5 10.75-19T288 256t18.125 8.5 10.75 19T320 304zm40 0q0-30-17.25-51T296 232q-10.25 0-48.75 5.25Q229.5 240 208 240t-39.25-2.75Q130.75 232 120 232q-29.5 0-46.75 21T56 304q0 22 8 38.375t20.25 25.75 30.5 15 35 7.375 37.25 1.75h42q20.5 0 37.25-1.75t35-7.375 30.5-15 20.25-25.75T360 304zm56-44q0 51.75-15.25 82.75-9.5 19.25-26.375 33.25t-35.25 21.5-42.5 11.875-42.875 5.5T212 416q-19.5 0-35.5-.75t-36.875-3.125-38.125-7.5-34.25-12.875T37 371.5t-21.5-28.75Q0 312 0 260q0-59.25 34-99-6.75-20.5-6.75-42.5 0-29 12.75-54.5 27 0 47.5 9.875t47.25 30.875Q171.5 96 212 96q37 0 70 8 26.25-20.5 46.75-30.25T376 64q12.75 25.5 12.75 54.5 0 21.75-6.75 42 34 40 34 99.5z"/></svg>
        
      </defs>
    </svg>
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" data-md-component="overlay" for="__drawer"></label>
    
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid">
    <div class="md-flex">
      <div class="md-flex__cell md-flex__cell--shrink">
        <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" aria-label="Hrbust_ACM's Wiki" class="md-header-nav__button md-logo">
          
            <i class="md-icon"></i>
          
        </a>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        <label class="md-icon md-icon--menu md-header-nav__button" for="__drawer"></label>
      </div>
      <div class="md-flex__cell md-flex__cell--stretch">
        <div class="md-flex__ellipsis md-header-nav__title" data-md-component="title">
          
            <span class="md-header-nav__topic">
              Hrbust_ACM's Wiki
            </span>
            <span class="md-header-nav__topic">
              
                ISAP算法
              
            </span>
          
        </div>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        
          <label class="md-icon md-icon--search md-header-nav__button" for="__search"></label>
          
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" aria-label="search" name="query" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="query" data-md-state="active">
      <label class="md-icon md-search__icon" for="__search"></label>
      <button type="reset" class="md-icon md-search__icon" data-md-component="reset" tabindex="-1">
        &#xE5CD;
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="result">
          <div class="md-search-result__meta">
            键入以开始搜索
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
        
      </div>
      
        <div class="md-flex__cell md-flex__cell--shrink">
          <div class="md-header-nav__source">
            


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
          </div>
        </div>
      
    </div>
  </nav>
</header>
    
    <div class="md-container">
      
        
      
      
        

  

<nav class="md-tabs md-tabs--active" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../.." class="md-tabs__link">
          首页
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../S/DFS/" class="md-tabs__link">
          搜索
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" class="md-tabs__link">
          动态规划
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" class="md-tabs__link">
          数据结构
        </a>
      
    </li>
  

      
        
  
  
    
    
  
  
    <li class="md-tabs__item">
      
        <a href="../%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" class="md-tabs__link">
          图论
        </a>
      
    </li>
  

  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" class="md-tabs__link">
          字符串
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" class="md-tabs__link">
          计算几何
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Others/Time/" class="md-tabs__link">
          附录
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
      
      <main class="md-main" role="main">
        <div class="md-main__inner md-grid" data-md-component="container">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" data-md-level="0">
  <label class="md-nav__title md-nav__title--site" for="__drawer">
    <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" class="md-nav__button md-logo">
      
        <i class="md-icon"></i>
      
    </a>
    Hrbust_ACM's Wiki
  </label>
  
    <div class="md-nav__source">
      


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-1" type="checkbox" id="nav-1">
    
    <label class="md-nav__link" for="nav-1">
      首页
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-1">
        首页
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../.." title="Getting Started" class="md-nav__link">
      Getting Started
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../home/" title="Wiki介绍" class="md-nav__link">
      Wiki介绍
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../faq/" title="如何使用" class="md-nav__link">
      如何使用
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-2" type="checkbox" id="nav-2">
    
    <label class="md-nav__link" for="nav-2">
      搜索
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-2">
        搜索
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DFS/" title="深度优先搜索" class="md-nav__link">
      深度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/BFS/" title="广度优先搜索" class="md-nav__link">
      广度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DeSearch/" title="双向搜索" class="md-nav__link">
      双向搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/Memory_Search/" title="记忆化搜索" class="md-nav__link">
      记忆化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alpha-beta%E5%89%AA%E6%9E%9D/" title="极大极小化搜索" class="md-nav__link">
      极大极小化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2/" title="启发式搜索" class="md-nav__link">
      启发式搜索
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-3" type="checkbox" id="nav-3">
    
    <label class="md-nav__link" for="nav-3">
      动态规划
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-3">
        动态规划
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" title="状态压缩DP" class="md-nav__link">
      状态压缩DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A0%91%E5%BD%A2DP/" title="树形 DP" class="md-nav__link">
      树形 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E5%8C%BA%E9%97%B4DP/" title="区间 DP" class="md-nav__link">
      区间 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%95%B0%E4%BD%8DDP/" title="数位 DP" class="md-nav__link">
      数位 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A6%82%E7%8E%87DP/" title="概率 DP" class="md-nav__link">
      概率 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%9C%9F%E6%9C%9BDP/" title="期望 DP" class="md-nav__link">
      期望 DP
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4" type="checkbox" id="nav-4">
    
    <label class="md-nav__link" for="nav-4">
      数据结构
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-4">
        数据结构
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" title="一维树状数组" class="md-nav__link">
      一维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%842/" title="二维树状数组" class="md-nav__link">
      二维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/ST/" title="ST表" class="md-nav__link">
      ST表
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/RMQ/" title="RMQ" class="md-nav__link">
      RMQ
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-5" type="checkbox" id="nav-4-5">
    
    <label class="md-nav__link" for="nav-4-5">
      线段树
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-5">
        线段树
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91lazy/" title="线段树lazy标记" class="md-nav__link">
      线段树lazy标记
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6/" title="线段树区间合并" class="md-nav__link">
      线段树区间合并
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%89%AB%E6%8F%8F%E7%BA%BF/" title="扫描线" class="md-nav__link">
      扫描线
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-6" type="checkbox" id="nav-4-6">
    
    <label class="md-nav__link" for="nav-4-6">
      树链剖分
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-6">
        树链剖分
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%A8/" title="点剖" class="md-nav__link">
      点剖
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%BE%B9%E5%89%96/" title="边剖" class="md-nav__link">
      边剖
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E5%88%86%E5%9D%97/" title="分块算法" class="md-nav__link">
      分块算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%8E%AB%E9%98%9F/" title="莫队算法" class="md-nav__link">
      莫队算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%86%E6%B2%BB/" title="点分治" class="md-nav__link">
      点分治
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5" checked>
    
    <label class="md-nav__link" for="nav-5">
      图论
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        图论
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-1" type="checkbox" id="nav-5-1">
    
    <label class="md-nav__link" for="nav-5-1">
      二分图
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-1">
        二分图
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" title="匈牙利算法" class="md-nav__link">
      匈牙利算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../KM%E7%AE%97%E6%B3%95/" title="KM 算法" class="md-nav__link">
      KM 算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-2" type="checkbox" id="nav-5-2" checked>
    
    <label class="md-nav__link" for="nav-5-2">
      网络流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-2">
        网络流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../EK/" title="EK 算法" class="md-nav__link">
      EK 算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../Dinic/" title="Dinic+当前弧优化" class="md-nav__link">
      Dinic+当前弧优化
    </a>
  </li>

        
          
          
          

  


  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-toggle md-nav__toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
    
    <a href="./" title="ISAP算法" class="md-nav__link md-nav__link--active">
      ISAP算法
    </a>
    
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-3" type="checkbox" id="nav-5-3">
    
    <label class="md-nav__link" for="nav-5-3">
      费用流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-3">
        费用流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../SPFA%E8%B4%B9%E7%94%A8%E6%B5%81/" title="SPFA 费用流" class="md-nav__link">
      SPFA 费用流
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      字符串
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        字符串
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" title="字典树" class="md-nav__link">
      字典树
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="AC自动机" class="md-nav__link">
      AC自动机
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7">
    
    <label class="md-nav__link" for="nav-7">
      计算几何
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        计算几何
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" title="点积叉积的运用" class="md-nav__link">
      点积叉积的运用
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%87%B8%E5%8C%85%E7%9A%84%E6%B1%82%E5%8F%96/" title="凸包的求取" class="md-nav__link">
      凸包的求取
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4/" title="半平面交" class="md-nav__link">
      半平面交
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E6%97%8B%E8%BD%AC%E5%8D%A1%E5%A3%B3/" title="旋转卡壳" class="md-nav__link">
      旋转卡壳
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      附录
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        附录
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/Time/" title="时间/空间复杂度" class="md-nav__link">
      时间/空间复杂度
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/exem/" title="习题" class="md-nav__link">
      习题
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                  <a href="https://github.com/acm-hrbust-wiki/wiki/tree/docs/Graph/ISAP.md" title="编辑此页" class="md-icon md-content__icon">&#xE3C9;</a>
                
                
                  <h1>ISAP算法</h1>
                
                <table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="c1">//洛谷 P3376</span>
<span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">INF</span> <span class="o">=</span> <span class="mf">2e9</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="mf">2e4</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">M</span> <span class="o">=</span> <span class="mf">2e5</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">base</span> <span class="o">=</span> <span class="mi">100</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">edge</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">to</span><span class="p">,</span> <span class="n">nex</span><span class="p">,</span> <span class="n">cap</span><span class="p">;</span>
    <span class="n">edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">to</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="kt">int</span> <span class="n">nex</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cap</span> <span class="o">=</span> <span class="mi">0</span><span class="p">)</span> <span class="o">:</span> <span class="n">to</span><span class="p">(</span><span class="n">to</span><span class="p">),</span> <span class="n">nex</span><span class="p">(</span><span class="n">nex</span><span class="p">),</span> <span class="n">cap</span><span class="p">(</span><span class="n">cap</span><span class="p">)</span> <span class="p">{}</span>
<span class="p">};</span>
<span class="k">class</span> <span class="nc">ISAP</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">head</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">d</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">cur</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">gap</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
    <span class="n">edge</span> <span class="n">e</span><span class="p">[</span><span class="n">M</span><span class="p">];</span>
    <span class="kt">void</span> <span class="nf">addedge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cap</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">e</span><span class="p">[</span><span class="o">++</span><span class="n">cnt</span><span class="p">]</span> <span class="o">=</span> <span class="n">edge</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">cap</span><span class="p">);</span>
        <span class="mi">63</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="c1">// 建图</span>
    <span class="kt">void</span> <span class="nf">buildGraph</span><span class="p">(</span><span class="kt">int</span> <span class="n">_n</span><span class="p">,</span> <span class="kt">int</span> <span class="n">_m</span><span class="p">,</span> <span class="kt">int</span> <span class="n">_S</span><span class="p">,</span> <span class="kt">int</span> <span class="n">_T</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="c1">// 初始化部分</span>
        <span class="n">n</span> <span class="o">=</span> <span class="n">_n</span><span class="p">;</span>
        <span class="n">m</span> <span class="o">=</span> <span class="n">_m</span><span class="p">;</span>
        <span class="n">S</span> <span class="o">=</span> <span class="n">_S</span><span class="p">;</span>
        <span class="n">T</span> <span class="o">=</span> <span class="n">_T</span><span class="p">;</span>
        <span class="n">mem</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
        <span class="n">cnt</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="c1">// 构图部分</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">cap</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">read</span><span class="p">(</span><span class="n">u</span><span class="p">);</span>
            <span class="n">read</span><span class="p">(</span><span class="n">v</span><span class="p">);</span>
            <span class="n">read</span><span class="p">(</span><span class="n">cap</span><span class="p">);</span>
            <span class="n">addedge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">cap</span><span class="p">);</span>
            <span class="n">addedge</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="c1">// 找增广路</span>
    <span class="kt">void</span> <span class="nf">bfs</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">cur</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">gap</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">T</span><span class="p">);</span>
        <span class="n">d</span><span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="o">=</span> <span class="n">gap</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">u</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span>
            <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nex</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">v</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">to</span><span class="p">;</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
                    <span class="k">continue</span><span class="p">;</span>
                <span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
                <span class="o">++</span><span class="n">gap</span><span class="p">[</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]];</span>
                <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">v</span><span class="p">);</span>
            <span class="p">}</span>
            <span class="mi">64</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">flow</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">u</span> <span class="o">==</span> <span class="n">T</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">flow</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">delta</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">temp</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">=</span> <span class="n">cur</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nex</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">v</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">to</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">!=</span> <span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">])</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">temp</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">min</span><span class="p">(</span><span class="n">flow</span> <span class="o">-</span> <span class="n">delta</span><span class="p">,</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">cap</span><span class="p">));</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">temp</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">cap</span> <span class="o">-=</span> <span class="n">temp</span><span class="p">;</span>
                <span class="n">e</span><span class="p">[</span><span class="n">i</span> <span class="o">^</span> <span class="mi">1</span><span class="p">].</span><span class="n">cap</span> <span class="o">+=</span> <span class="n">temp</span><span class="p">;</span>
                <span class="n">delta</span> <span class="o">+=</span> <span class="n">temp</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">flow</span> <span class="o">==</span> <span class="n">delta</span><span class="p">)</span>
                <span class="k">return</span> <span class="n">flow</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="o">--</span><span class="n">gap</span><span class="p">[</span><span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]]))</span>
            <span class="n">d</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="o">++</span><span class="n">gap</span><span class="p">[</span><span class="o">++</span><span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]];</span>
        <span class="n">cur</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span>
        <span class="k">return</span> <span class="n">delta</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">get_maxFlow</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">bfs</span><span class="p">();</span>
        <span class="kt">int</span> <span class="n">maxFlow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">)</span>
            <span class="n">maxFlow</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">INF</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">maxFlow</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="n">ISAP</span> <span class="n">ways</span><span class="p">;</span>
<span class="kt">signed</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="o">~</span><span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d%d%d%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">n</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">m</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">S</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">T</span><span class="p">))</span>
    <span class="p">{</span>
        <span class="n">ways</span><span class="p">.</span><span class="n">buildGraph</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">);</span>
        <span class="mi">65</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">ways</span><span class="p">.</span><span class="n">get_maxFlow</span><span class="p">());</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<p><strong>例题：</strong>网络流 24 题 星际转移 Loj 6015 </p>
<blockquote>
<p><strong>题意：</strong>现有 n 个太空站位于地球与月球之间，且有 m 艘公共交通太空船在其间来回 穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 Hi 个人。每艘太空船将 周期性地停靠一系列的太空站，例如：1,3,4 表示该太空船将周期性地停靠太空站 134134134⋯ 每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停 靠太空站（或月球、地球）时上、下船。 初始时所有人全在地球上，太空船全在初始站。 试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。 </p>
</blockquote>
<p><strong>分析：</strong>这个题其实和“魔术球”这个题类似。题意就相当于一些人要从 A ---&gt; B ，空间 站为中转点，通过飞船转移，这些飞船每一天出现在固定空间站，也即是说天数不一定的时 候，整个运输图就会发生变化，而每一天之间又是有关系的。</p>
<p>就好像，每一天的空间站是不 一样的（因为飞船飞行线路不一样了），所以考虑到 地球（0 号点）、n 个空间站和月亮（n + 1 号点）共 n + 2 个点，每一天分裂一次（即拥有一个新的状态），有因为共经历 t 天， 完成运输，故 将要分裂出 <code>t * (n + 2)</code> 个点【即是说将每一天的这 n + 2 个点看成一个新的 点】，枚举每一天 day，令<code>yesterday = (n + 2) * (day – 1)，today = (n + 2) * day；</code>则每一个 点 <code>i’ = yesterday + i</code>（代表昨天对应的点）,<code>i = today + i</code>（代表今天的点）；故<code>i’---&gt;i</code>，容 量为 INF，<code>(n + 1) + today ---&gt; T</code>，容量为 INF; 在从每一个飞船前一天所在的太空站连向后一天的太空站，流量为飞船可容纳人 数； 在最开始的时候 链接一条， <code>S ----&gt; 0</code>，容量为 INF 的边 跑最大流直到不小于总人数即可。（每一天的最大流应累加起来）</p>
<table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="cp">#pragma GCC optimize(2)</span>
<span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span>
<span class="cp">#define read(a) scanf(&quot;%d&quot;, &amp;a)</span>
<span class="cp">#define readl(a) scanf(&quot;%lld&quot;, &amp;a)</span>
<span class="cp">#define reads(a) scanf(&quot;%s&quot;, a)</span>
<span class="cp">#define readc(a) scanf(&quot;%c&quot;, &amp;a)</span>
<span class="cp">#define pb push_back</span>
<span class="cp">#define mem(a) memset(a, 0, sizeof(a))</span>
<span class="cp">#define Buff ios::sync_with_stdio(false)</span>
<span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">INF</span> <span class="o">=</span> <span class="mf">2e9</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="mf">1e5</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">M</span> <span class="o">=</span> <span class="mf">1e6</span> <span class="o">+</span> <span class="mi">7</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">_N</span> <span class="o">=</span> <span class="mi">102</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">base</span> <span class="o">=</span> <span class="mi">100</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">edge</span> <span class="mi">66</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">to</span><span class="p">,</span> <span class="n">nex</span><span class="p">,</span> <span class="n">cap</span><span class="p">;</span>
    <span class="n">edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">to</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="kt">int</span> <span class="n">nex</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cap</span> <span class="o">=</span> <span class="mi">0</span><span class="p">)</span> <span class="o">:</span> <span class="n">to</span><span class="p">(</span><span class="n">to</span><span class="p">),</span> <span class="n">nex</span><span class="p">(</span><span class="n">nex</span><span class="p">),</span> <span class="n">cap</span><span class="p">(</span><span class="n">cap</span><span class="p">)</span> <span class="p">{}</span>
<span class="p">};</span>
<span class="kt">int</span> <span class="n">pre</span><span class="p">[</span><span class="n">_N</span><span class="p">],</span> <span class="n">station</span><span class="p">[</span><span class="n">_N</span><span class="p">][</span><span class="n">_N</span><span class="p">],</span> <span class="n">r</span><span class="p">[</span><span class="n">_N</span><span class="p">],</span> <span class="n">H</span><span class="p">[</span><span class="n">_N</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">head</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">d</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">cur</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">gap</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="n">edge</span> <span class="n">e</span><span class="p">[</span><span class="n">M</span><span class="p">];</span>
<span class="k">class</span> <span class="nc">ISAP</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">K</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">addedge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cap</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">e</span><span class="p">[</span><span class="o">++</span><span class="n">cnt</span><span class="p">]</span> <span class="o">=</span> <span class="n">edge</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">cap</span><span class="p">);</span>
        <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">;</span>
        <span class="n">e</span><span class="p">[</span><span class="o">++</span><span class="n">cnt</span><span class="p">]</span> <span class="o">=</span> <span class="n">edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">head</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="mi">0</span><span class="p">);</span>
        <span class="n">head</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">;</span>
        <span class="c1">// printf(&quot;%d --- %d, %d\n&quot;, u, v, cap);</span>
    <span class="p">}</span>
    <span class="c1">// 建图</span>
    <span class="kt">void</span> <span class="nf">buildGraph</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="c1">// 初始化部分</span>
        <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
        <span class="n">read</span><span class="p">(</span><span class="n">m</span><span class="p">);</span>
        <span class="n">read</span><span class="p">(</span><span class="n">K</span><span class="p">);</span>
        <span class="n">mem</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
        <span class="n">cnt</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">S</span> <span class="o">=</span> <span class="n">N</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span>
        <span class="n">T</span> <span class="o">=</span> <span class="n">N</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">read</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
            <span class="n">read</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span>
                <span class="n">read</span><span class="p">(</span><span class="n">station</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span>
            <span class="n">pre</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">n</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span>
        <span class="n">addedge</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">INF</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">day</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">day</span> <span class="o">&lt;=</span> <span class="mi">30</span><span class="p">;</span> <span class="n">day</span><span class="o">++</span><span class="p">)</span>
            <span class="mi">67</span>
            <span class="p">{</span>
                <span class="kt">int</span> <span class="n">today</span> <span class="o">=</span> <span class="n">n</span> <span class="o">*</span> <span class="n">day</span><span class="p">,</span> <span class="n">yesterday</span> <span class="o">=</span> <span class="n">n</span> <span class="o">*</span> <span class="p">(</span><span class="n">day</span> <span class="o">-</span> <span class="mi">1</span><span class="p">),</span> <span class="n">now</span><span class="p">;</span>
                <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
                    <span class="n">addedge</span><span class="p">(</span><span class="n">yesterday</span> <span class="o">+</span> <span class="n">i</span><span class="p">,</span> <span class="n">today</span> <span class="o">+</span> <span class="n">i</span><span class="p">,</span> <span class="n">INF</span><span class="p">);</span>
                <span class="n">addedge</span><span class="p">(</span><span class="n">today</span> <span class="o">+</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">T</span><span class="p">,</span> <span class="n">INF</span><span class="p">);</span>
                <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
                <span class="p">{</span>
                    <span class="n">now</span> <span class="o">=</span> <span class="n">pre</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">now</span> <span class="o">&gt;</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
                        <span class="n">now</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
                    <span class="n">addedge</span><span class="p">(</span><span class="n">station</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">pre</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">+</span> <span class="n">yesterday</span><span class="p">,</span> <span class="n">station</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">now</span><span class="p">]</span> <span class="o">+</span> <span class="n">today</span><span class="p">,</span> <span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
                    <span class="n">pre</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span>
                <span class="p">}</span>
                <span class="n">ans</span> <span class="o">+=</span> <span class="n">get_maxFlow</span><span class="p">();</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">ans</span> <span class="o">&gt;=</span> <span class="n">K</span><span class="p">)</span>
                <span class="p">{</span>
                    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">day</span><span class="p">);</span>
                    <span class="k">return</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="c1">// 找增广路</span>
    <span class="kt">void</span> <span class="nf">bfs</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">T</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">cur</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">gap</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">T</span><span class="p">);</span>
        <span class="n">d</span><span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="o">=</span> <span class="n">gap</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">u</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span>
            <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nex</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">v</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">to</span><span class="p">;</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
                    <span class="k">continue</span><span class="p">;</span>
                <span class="mi">68</span> <span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
                <span class="o">++</span><span class="n">gap</span><span class="p">[</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]];</span>
                <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">v</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">flow</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">u</span> <span class="o">==</span> <span class="n">T</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">flow</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">delta</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">temp</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">=</span> <span class="n">cur</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nex</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">v</span> <span class="o">=</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">to</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">!=</span> <span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">])</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">temp</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">min</span><span class="p">(</span><span class="n">flow</span> <span class="o">-</span> <span class="n">delta</span><span class="p">,</span> <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">cap</span><span class="p">));</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">temp</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">cap</span> <span class="o">-=</span> <span class="n">temp</span><span class="p">;</span>
                <span class="n">e</span><span class="p">[</span><span class="n">i</span> <span class="o">^</span> <span class="mi">1</span><span class="p">].</span><span class="n">cap</span> <span class="o">+=</span> <span class="n">temp</span><span class="p">;</span>
                <span class="n">delta</span> <span class="o">+=</span> <span class="n">temp</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">flow</span> <span class="o">==</span> <span class="n">delta</span><span class="p">)</span>
                <span class="k">return</span> <span class="n">flow</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="o">--</span><span class="n">gap</span><span class="p">[</span><span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]]))</span>
            <span class="n">d</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="n">T</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="o">++</span><span class="n">gap</span><span class="p">[</span><span class="o">++</span><span class="n">d</span><span class="p">[</span><span class="n">u</span><span class="p">]];</span>
        <span class="n">cur</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span>
        <span class="k">return</span> <span class="n">delta</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">get_maxFlow</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">bfs</span><span class="p">();</span>
        <span class="kt">int</span> <span class="n">maxFlow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">T</span><span class="p">)</span>
            <span class="n">maxFlow</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">INF</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">maxFlow</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="mi">69</span> <span class="n">ISAP</span> <span class="n">ways</span><span class="p">;</span>
<span class="kt">signed</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">ways</span><span class="p">.</span><span class="n">buildGraph</span><span class="p">();</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<p>整理人：网络 18-3 高云泽</p>
                
                  
                
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid">
        
          <a href="../Dinic/" title="Dinic+当前弧优化" class="md-flex md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-back md-footer-nav__button"></i>
            </div>
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  上一页
                </span>
                Dinic+当前弧优化
              </span>
            </div>
          </a>
        
        
          <a href="../SPFA%E8%B4%B9%E7%94%A8%E6%B5%81/" title="SPFA 费用流" class="md-flex md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  下一页
                </span>
                SPFA 费用流
              </span>
            </div>
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-forward md-footer-nav__button"></i>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
        powered by
        <a href="https://www.mkdocs.org" target="_blank" rel="noopener">MkDocs</a>
        and
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs</a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/application.c33a9706.js"></script>
      
        
        
          
          <script src="../../assets/javascripts/lunr/lunr.stemmer.support.js"></script>
          
            
              
                <script src="../../assets/javascripts/lunr/tinyseg.js"></script>
              
              
                <script src="../../assets/javascripts/lunr/lunr.ja.js"></script>
              
            
          
          
        
      
      <script>app.initialize({version:"1.1",url:{base:"../.."}})</script>
      
        <script src="https://cdnjs.loli.net/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>